package com.yb0os1;


import org.w3c.dom.Node;

public class MyHashMap<K, V> {
    //默认的初始容量
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    //默认的负载因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //当前HashMap的大小
    private int size;

    //存储Node的数组
    private Node<K, V>[] table;
    //负载因子
    private float loadFactor;

    public MyHashMap() {
        this.size = 0;
        this.table = new Node[DEFAULT_INITIAL_CAPACITY];
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

    public V put(K key, V value) {
        //put的时候，首先获取key的hashcode计算对应的indexOf
        int index = indexOf(key);
        Node<K, V> head = table[index];
        //判断数组当前index是否为空
        if (head == null) {//为空
            table[index] = new Node<>(key, value);
            size++;
            resizeIfNecessary();
            return null;
        }
        //当前数组下标位置不为空
        while (true) {
            //当前位置key和传入的key相同，替换value
            if (head.key.equals(key)) {
                V oldValue = head.value;
                head.value = value;
                return oldValue;
            }
            //当前位置key和传入的key不相同，先判断是否到链表尾部
            if (head.next == null) {
                head.next = new Node<>(key, value);
                size++;
                resizeIfNecessary();
                return null;
            }
            //继续遍历下一个节点
            head = head.next;
        }
    }


    public V get(K key) {
        //get的时候，首先获取key的hashcode计算对应的indexOf
        int index = indexOf(key);
        Node<K, V> head = table[index];
        //判断数组当前index是否为空
        while (head != null){
            if(head.key.equals(key)){
                return head.value;
            }
            head = head.next;
        }
        return null;
    }

    public V remove(K key) {
        //remove的时候，首先获取key的hashcode计算对应的indexOf
        int index = indexOf(key);
        Node<K,V> head = table[index];
        //要判断是否为头节点
        //是头节点
        if(head!=null&&head.key.equals(key)){
            table[index] = head.next;
            --size;
            return head.value;
        }
        //不为头节点
        Node<K,V> pre = head;
        Node<K,V> cur = head.next;
        while(cur!=null){
            if(cur.key.equals(key)){
                pre.next=cur.next;
                --size;
                return cur.value;
            }
            pre = cur;
            cur  = cur.next;
        }
        return null;
    }
    public int size(){
        return size;
    }
    private int indexOf(Object key) {
        return key.hashCode() & (table.length - 1);
    }

    private void resizeIfNecessary() {
        //不需要扩容的情况
        if(size<table.length*loadFactor)return;
        //需要扩容的情况 新建一个新的桶数组
        Node<K,V>[] newTable = new Node[table.length*2];
        //遍历老的桶数组，将原先的元素再哈希放到新的桶数组
        for(Node<K,V> head:table){
            if ( head==null)continue;
            Node<K,V>current = head;
            while(current!=null){
                //获取当前元素在新的桶数组中的index
                int newIndex = current.key.hashCode() & (newTable.length-1);
                if( newTable[newIndex]==null){
                    newTable[newIndex] = current;
                    Node< K,V>next = current.next;
                    current.next = null;
                    current = next;
                }else{
                    //头插法
                    Node< K,V>next =current.next;
                    current.next = newTable[newIndex];
                    newTable[newIndex] = current;
                    current = next;
                }
            }
        }
        this.table = newTable;
        System.out.println( "扩容了"+ table.length);
    }

    //hashmap里面的节点 entry
    private class Node<K, V> {
        public Node() {

        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K key;
        public V value;
        public Node<K,V> next;
    }
}
